The present invention relates to a computer graphics rendering method and apparatus.
Computer graphics rendering has been used widely in video games, car navigation systems, etc. In a video game, it is desirable that an object to be rendered, such as a human character, a car and a background object, is rendered beautifully in a realistic manner. In a car navigation system, it is desirable that an object to be rendered, such as a road, a building and a geographical feature, is rendered so that the rendered image is readily understood by the user. In order for the rendered image to be more realistic or more readily understandable, it is desirable that each object is rendered precisely at its intended position.
In order to display a three-dimensional (3D) image, it is necessary to perform hidden surface removal based on a point of view so as to render visible portions of a shape and not to render invisible portions thereof. The Z-buffer method is a conventional method for hidden surface removal. In the z-buffer method, a Z buffer is provided for storing the “Z value” representing the depth of each pixel on the display screen.
The Z value is also defined for each pixel of a shape to be rendered. Then, the Z value of each pixel of the shape being rendered is compared with that of the same pixel in the Z buffer, and pixel data with a smaller Z value (i.e., pixel data closer to the viewer) is displayed. The hidden surface removal operation is performed as described above.
A conventional line segment rendering method will now be described. The DDA (Digital Differential Analyzer) method is commonly used as a method for rendering a line segment.
Referring to FIG. 6, where the start point position Ps of a line segment is (Xs, Ys, Zs) and the end point position Pe thereof is (Xe, Ye, Ze), the process will be referred to as “DDA in the X direction” if |Xe−Xs|≧|Ye−Ys| and as “DDA in the Y direction” if |Xe−Xs|<|Ye−Ys|.
In the DDA in the X direction, the gradients dYdX=(Ye−Ys)/|Xe−Xs| and dZdX=(Ze−Zs)/|Xe−Xs| are calculated assuming L=|Xe−Xs|, and the next point P1 to be rendered after the start point Ps is calculated by P1=(X1, Y1, Z1)=(Xs+|Xe−Xs|/(Xe−Xs), Ys+dYdX, Zs+dZdX). Thereafter, the next point Pj to be rendered after the current point Pi is calculated by Pj=(Xj, Yj, Zj)=(Xi+|Xe−Xs|/(Xe−Xs), Yi+dYdX, Zi+dZdX), and the process is repeated until the X coordinate Xj is equal to Xe.
In the DDA in the Y direction, the gradients dXdY=(Xe−Xs)/|Ye−Ys| and dZdY=(Ze−Zs)/|Ye−Ys| are calculated assuming L=|Ye−Ys|, and the next point P1 to be rendered after the start point Ps is calculated by P1=(X1, Y1, Z1)=(Xs+dXdY, Ys+|Ye−Ys|/(Ye−Ys), Zs+dZdY). Thereafter, the next point Pj to be rendered after the current point Pi is calculated by Pj=(Xj, Yj, Zj)=(Xi+dXdY, Yi+|Ye−Ys|/(Ye−Ys), Zi+dZdY), and the process is repeated until the Y coordinate Yj is equal to Ye. In FIG. 6, the value in each box represents the calculated Z value of that point.
A DDA method described below is commonly used as a method for rendering a trapezoid, including a rectangular or a triangle as a variation thereof.
Referring to FIG. 7, where a trapezoid has the left-side start point position Pls =(Xls, Ys, Zls), the right-side start point position Prs=(Xrs, Ys, Zrs), the left-side end point position Ple=(Xle, Ye, Zle) and the right-side end point position Pre=(Xre, Ye, Zre), the gradients dXldY=(Xle−Xls)/|Ye−Ys|, dXrdY=(Xre−Xrs)/|Ye−Ys|, dZldY=(Zle−Zls)/|Ye−Ys|and dZdX=(Zrs−Zls)/(Xrs−Xls) are calculated in the DDA method. First, the horizontal portion where Y=Ys is rendered. Assume the leftmost point of this portion is Pl(Xl, Y, Zl) and the rightmost point thereof is (Xr, Y, Zr). First, assuming Xl=Xls, Xr=Xrs, Y=Ys and Zl=Zls, the leftmost point is rendered. The next point P1 to be rendered is calculated by P1=(X, Y, Z)=(Xls+1, Ys, Zls+dZdX). Thereafter, the next point Pj to be rendered after the current point Pi is calculated by Pj=(Xj, Yj)=(Xi+1, Ys, Zi+dZdX), and the process is repeated until the X coordinate Xj is equal to Xr. Then, Y is incremented by 1, and the process proceeds to the next portion below. Where the leftmost point is Pl(Xl, Y, Zl), it is assumed Xl=Xl+dXldY, Y=Y+1, Z=Zl+dZldY and Xr=Xr+dXrdY, and the process of adding 1 and dZdX in the X direction as described above is repeated until the X coordinate reaches the rightmost value Xr. This series of operations are repeated until Y is equal to Ye. Thus, a quadrilateral is rendered. In FIG. 7, the value in each box represents the calculated Z value of that point.
However, a problem arises when rendering a line over a coplanar rendered quadrilateral with the conventional rendering method as described above with hidden surface removal with reference to Z values, the Z value of one point along the line as calculated when rendering the line may differ from that of the same point as calculated when rendering the quadrilateral, even though the line segment and the quadrilateral are coplanar with each other. Then, in many cases, the line is inappropriately rendered over the quadrilateral. For example, under a rule where a new Z value of a point replaces the previous Z value of that point if the new Z value is less than or equal to the previous Z value, rendering the line of FIG. 6 over the trapezoid of FIG. 7 yields a result as shown in FIG. 8, indicating that the line is not appropriately rendered over the trapezoid.
Where two coplanar shapes share some pixels with each other, the two shapes should theoretically share the same Z value for each of those pixels. However, the calculated Z value for one shape may differ from that for the other shape. Then, some pixels of one shape that are supposed to be displayed may not be displayed.
In view of this, Japanese Laid-Open Patent Publication No. 2001-167291, for example, discloses a method in which a constant offset Z value is added to, or subtracted from, the Z value of each pixel of one of two coplanar shapes that is intended to be rendered closer to the viewer than the other shape.
However, this method also has a problem in that the two shapes may not be rendered properly as to which is rendered over the other, depending on the magnitude relationship between the constant offset Z value and the Z values calculated while rendering a line segment and a quadrilateral.